/*
 * arvore.c
 *
 *  Created on: 05/06/2011
 *      Author: joao
 */

#include "arvore.h"


/* Rotacao a direita */
void rot_dir(no **p) {
    no *aux;
    aux = (*p)->esq;
    (*p)->esq = aux->dir;
    aux->dir = *p;
    *p = aux;
}

/* Rotacao a esquerda */
void rot_esq(no **p) {
    no *aux;
    aux = (*p)->dir;
    (*p)->dir = aux->esq;
    aux->esq = *p;
    *p = aux;
}


/* Insercao na Arvore */
int insereAVL(char *x, no **p, TipoElemento linha) {
    int cresceu;
    /* Se a arvore esta vazia insere. */
    if (*p == NULL) {
        *p = (no *) malloc(sizeof(no));
        (*p)->chave = x;
        (*p)->quantidade = 1;
        Cria(&(*p)->linhas);
        Adiciona(linha, &(*p)->linhas);
        /* Caso houvesse outros dados eles deveriam ser copiados aqui. */
        (*p)->dir = (*p)->esq = NULL;
        /* Balanceamento de uma folha e sempre perfeito */
        (*p)->bal = 0;
        /* Esta sub arvore cresceu */
        cresceu = 1;
        }
        /* Senao verifica se tem que inserir a esquerda */
        else if (strcmp((*p)->chave, x) > 0) {
            /* Tenta inserir a esquerda e ve se a sub-arvore cresceu */
            cresceu = insereAVL(x, &(*p)->esq, linha);
            if (cresceu) {

                /* Verifica o estado atual de balanceamento */
                switch((*p)->bal) {

                    /* Se a arvore dir. era maior nao ha crescimento */
                    case 1:
                        (*p)->bal = 0;
                        cresceu = 0;
                    break;

                    /* Se a arvore dir. tinha tamanho igual, houve crescimento */
                    case 0:
                        (*p)->bal = -1;
                        cresceu = 1;
                        break;
                    /* Se a sub-arvore da esq. ja era maior, deve-se re-balancear. */
                    case -1:
                        /* Verifica qual o caso de re-balanceamento. */
                        /* Se a arvore da esquerda do filho da esquerda esta mais */
                        /* alta basta uma rotacao para direita. */
                        if ((*p)->esq->bal == -1) {
                            /* Rotacao para direita.*/
                            rot_dir(p);
                            /* Acerta os balanceamentos. */
                            (*p)->bal = (*p)->dir->bal = 0;
                        } else {
                            /* Rotacao dupla. */

                            /* Primeiro a esquerda. */
                            rot_esq(&(*p)->esq);
                            /* Depois a direita.*/
                            rot_dir(p);

                            /* Acerta balanceamentos. */
                            if ((*p)->bal == -1) {
                                (*p)->esq->bal = 0;
                                (*p)->dir->bal = 1;
                            } else {
                                (*p)->dir->bal = 0;
                                (*p)->esq->bal = -(*p)->bal;
                            }
                            (*p)->bal = 0;
                        }
                        cresceu = 0;
                }

            }
        }
        /* Verifica se tem que inserir a direita. */
        else if (strcmp((*p)->chave, x) < 0) {
            /* Tenta inserir a direita e ve se a sub-arvore cresceu */
            cresceu = insereAVL(x, &(*p)->dir, linha);
            if (cresceu) {
                /* Verifica o estado atual de balanceamento */
                switch((*p)->bal) {
                    /* Se a arvore esq. era maior nao ha crescimento */
                    case -1:
                        (*p)->bal = 0;
                        cresceu = 0;
                    break;
                    /* Se a arvore esq. tinha tamanho igual, houve crescimento */
                    case 0:
                        (*p)->bal = 1;
                        cresceu = 1;
                    break;
                    /* Se a arvore da dir. ja era maior, deve-se re-balancear. */
                    case 1:
                        /* Verifica qual o caso de re-balanceamento. */
                        /* Se a arvore da direita do filho da direita esta mais */
                        /* alta basta uma rotacao para esquerda. */
                        if ((*p)->dir->bal == 1) {
                            /* Rotacao para esquerda.*/
                            rot_esq(p);
                            /* Acerta os balanceamentos. */
                            (*p)->bal = (*p)->esq->bal = 0;
                        } else {
                            /* Rotacao dupla.*/

                            /* Primeiro a direita.*/
                            rot_dir(&(*p)->dir);
                            /* Depois a esquerda. */
                            rot_esq(p);

                            /* Acerta balanceamentos. */
                            if ((*p)->bal == -1) {
                                (*p)->esq->bal = 0;
                                (*p)->dir->bal = 1;
                            } else {
                                (*p)->dir->bal = 0;
                                (*p)->esq->bal = -(*p)->bal;
                            }

                            (*p)->bal = 0;
                        }
                        cresceu = 0;
                }
        }
    } else {
        cresceu = 0;
        (*p)->quantidade++;
        if (Localiza(linha, &(*p)->linhas) == FIM)
            Adiciona(linha, &(*p)->linhas);

    }
        return cresceu;
}

/* Imprime a arvore */
void imprime(no *raiz, int nivel) {
     int i;

     if (raiz == NULL){ return; }

     imprime(raiz->dir, nivel + 1);

     for(i = 0; i < nivel; i++) printf("   ");

     printf("%s(%d) ", raiz->chave, raiz->quantidade);
     ImprimeLista(&raiz->linhas);
     printf("\n");

     imprime(raiz->esq, nivel + 1);
}

/* Busca x em uma arvore binaria de busca. */
no *busca(char *x, no *raiz) {
   while ((raiz != NULL) && strcmp(raiz->chave, x) != 0) {
         if (strcmp(raiz->chave, x) < 0) raiz = raiz->dir;
            else raiz = raiz->esq;
   }
   return raiz;
}
